package 其他.叠积木;

import java.util.Arrays;

class Solution {

    //  K 代表 要分为多少份, 就是多少层
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k == 1) return true; // 特判
        Arrays.sort(nums);
        int n = nums.length;
        int target = 0;
        int max = 0;
        for (int i : nums) target += i;
        if (target % k != 0) return false; // 特判
        target /= k;  //target 每层长度
        // 如果每层长度 < 最大值, 返回 false
        if (target < nums[n - 1]) return false; // 特判
        int[] sums = new int[k];
        return dfs(nums, n - 1, 0, sums, k, target);
    }
    //
    private boolean dfs(int[] nums, int cur, int used, int[] sums, int k, int target) {

        if (cur < 0) {
            return true;
        }
        if (used < k) {
            sums[used] = nums[cur];
            if (dfs(nums, cur - 1, used + 1, sums, k, target)) return true;
            sums[used] = 0;
        }
        for (int i = 0; i < used; i++) {
            // 如果当前桶和上一个桶内的元素和相等，则跳过
            // 原因：如果元素和相等，那么 nums[cur] 选择上一个桶和选择当前桶可以得到的结果是一致的
            if (i > 0 && sums[i] == sums[i - 1]) continue;
            if (sums[i] + nums[cur] <= target) {
                sums[i] += nums[cur];
                if (dfs(nums, cur - 1, used, sums, k, target))
                    return true;
                sums[i] -= nums[cur];
            }
        }
        return false;
    }
}
